Traveling Companions
by Black Hole of Procrastination
Summary: In the seven years since she left him to die on the road to the Eyrie, he never imagined he would once again be riding through the bloody countryside with the Stark bitch in tow. Arya/Hound.
1. Traveling Companions

**Traveling Companions**

**Summary:** In the seven years since she left him to die on the road to the Eyrie, he never imagined he would once again be riding through the bloody countryside with the Stark bitch in tow. Arya/Hound. One-shot.

**Author's Note:** After SanSan fans didn't crucify me for my last Arya/Sandor effort, I thought I'd give it another go. This is a prequel of sorts to "You Remember Where The Heart Is?" though it also stands on its own. Arya and the Hound make such a dynamic traveling duo I thought I'd take them on the road again. Post-Faceless Men Arya is hard to grapple with as a writer, so I hope I did her justice. Let me know what you think! I'm also toying with a follow-up one-shot in Arya's POV, so keep an eye out for it.

**Traveling Companions**

In the seven years since she left him to die on the road to the Eyrie, he never imagined he would once again be riding through the bloody countryside with the Stark bitch in tow.

Of course, stranger things had come to pass in that time. Wildings lived south of the Wall, there were dragons in the Red Keep, and he was a Lannister dog once more.

It was the little bird's idea. He was meant to protect the girl on her journey North. The Stark bitch needed protection like a bull needed teats, but he'd not argue with the little bird.

Besides, his 'protection' was just as unnecessary in the Red Keep these days. The little bird was no longer a cowering maiden but a woman grown. She still chirped her songs but had learned different tunes, ones that raised armies and quelled queens.

He suspected his new charge was more a kindness to him than a courtesy to her sister. He'd been a true and loyal dog since he'd pledged his sword to the little bird in the Vale, but his post had become harder to man as of late. The physical evidence of the affection between Lord and Lady Lannister now quickened in her womb. And while the war had hardened Sansa, she was not entirely drained of sweetness and compassion. In sending him North, she had taken pity on her foolish old dog, sparing him from standing watch as she bore the Imp his lion cub.

As for the Stark bitch, she expressed no objection to the arrangement, only demanding they leave as soon as the roads were safe for travel. Her ready agreement with Sansa's plan was her own sort of kindness, an effort to preserve the tenuous peace between the sisters.

Arya had said precious little since she arrived at the Red Keep five moons ago, dirty and ragged with Aegon the Pretender's head in a sack. He'd wanted to hate the little bitch for leaving him on that road, for not showing him mercy. But as she dumped the head at the feet of the Dragon Queen, he felt something akin to pride stir within him for the brazen little chit.

Later, in the Tower of the Hand, away from the prying eyes of court, she had tossed him a purse of silver. It felt to be near the same amount she had lifted from his belt before she left him to rot.

"Am I still on your list then, girl?" he had asked, half japing and half wondering if his head was next in line to be tossed before the Iron Throne.

"I left you to die. It's not my fault if the seven hells wouldn't take you."

That had certainly ruffled the little bird's feathers, setting her chirping apologies and reprimands with equal fervor.

He had only barked out a laugh, before pocketing the coins. As far as he was concerned, the wolf bitch was the only highborn cunt left in seven kingdoms who wasn't completely full of shit.

They set out as the first thaw of spring takes hold. The countryside is flooded with water and mud, as the snow of the long winter melts, forming murky gullies along the edge of the Kingsroad. He is grateful to not have to make camp in the muck. Traveling on Lannister coin guarantees them a place in every featherbed from the capital to Winterfell.

She still travels as a boy, though anyone who believes it is a fucking fool. At nine-and-ten, she has long since been a woman flowered, even if she is not the beauty her sister is. Sansa is the Maiden come to life. Arya is the Stranger with teats.

She is taller (nearly to his chin now) but still as skinny as she ever was, all long Stark features and sharp angles, with no hints of womanly softness. Her dark hair has been cut bluntly at her chin, setting off owlish grey eyes and an overgenerous mouth. Still, he can't deny there's something striking about the Stark bitch.

At the start, they ride in silence. It suits him fine. Even after six years in the little bird's service, he's still can't stand idle chatter.

But it is a long ride to the walls of Winterfell, and as they put more distance between themselves and the Red Keep, Arya's tongue begins to loosen.

She tells him stories of the North, dark tales of magic and monsters passed on from some crone the girl calls Old Nan. Sometimes she shares bawdy jokes she picked up in the backrooms of taverns. Sometimes she sings.

She knows as many songs as the little bird, he'd wager, but they are not pretty tales of knights and maidens. The wolf bitch's songs are foul, violent, funny, and sad. A few are even in some damnable Eastern tongue (the only thing she shares of her time across the Narrow Sea).

He listens to it all.

A sennight into the journey, he begins to share a few tales of his own. He tells her of his time among the brothers on the Quiet Isle. He tells her about slaying that shit Littlefinger at the Eyrie before pledging his sword to Sansa. He even tells her about his battle with Gregor.

"Bastard still won in the end. I didn't kill him. I killed a beast that Cersei cobbled together from the husk of his flesh. Should have known the fucking Lannister bitch used black magic."

She offers neither comment nor consolation. If anyone knows what it is to be cheated of vengeance, it's Arya Stark.

By the time they reach the Neck, featherbeds are harder to come by. Their first night without an inn, they find dry ground away from the road and make camp, working in silence.

It has been a long time since he's had to sleep rough (his time at the Red Keep has made him soft) and sleep does not come easy. He's not the only one. He listens as the wolf bitch tosses and turns before rising to cross to his side of the fire.

"If you're going to kill me, make it quick," he mumbles, pulling his cloak closer to his chin. He nearly jumps out of his skin when he feels her lay next to him on his bedroll. "What are you doing, girl?"

"Getting warm, stupid," she snaps. "Move over."

He's sees the sense in it. They will both fair better in this damnable cold if they share each other's warmth. It's practical, clever even, but that does not make it any easier to ignore the lithe young body curled at his back.

The next night he finishes the last of the wine. There will be no resupplying their stores until the next village (a good three days ride) and his head will not thank him come morning, but he can't bring himself to care.

His head is buzzing so much, he hardly notices when she finally settles on the bedroll behind him—that is, until he feels a sharp tug at his tunic.

"Go the fuck to sleep, girl!" he growls, swatting her hand away. For a moment, he thinks that is the end of it, but then the stubborn bitch tugs at his hem once more.

He rolls over to face her, but chokes down the curses on his breath at the feel of soft lips pressed against his scarred ones.

He can count the times he's been kissed on one hand. Most whores can hardly look him in the eye, let alone touch his face. Then of course there was the night of the Blackwater; a kiss stolen from a pretty child with a knife at her throat.

But the wolf bitch has neither his coin in her pocket nor his blade at her flesh. She has no call to press against him this way, to tug at his hair, to kiss him. _No reason but want of him. _

The thought leaves him reeling even more than the wine, unbalancing all sense from his mind, so that when teeth playfully graze his lower lip, he responds in kind.

She is no maid, that much is for certain. Still, her movements are unpracticed as she reaches between them to fumble with the lacing on his breeches. He matches her in clumsy eagerness, nipping at the flesh of her neck while pawing at her jerkin and tunic until both pale breasts are unveiled to the cold night air.

It's not until he's buried inside her that he dares to look her in the eye. He is prepared to be met with disgust, with pain, with anger. Instead, there's a strange softness about her gaze that leaves a twisting in his gut.

He wakes the next morning with a dry mouth, a fuzzy head, and the bedroll next to him empty. She's not gone far (a few paces beyond where the horses are tied), and she's water dancing.

In the morning light there's something unnatural about her. She looks more like a fae or woodland spirit from one of her damned stories. He watches as she gracefully moves through the air, cutting down imaginary foes. She's gotten better, her movements quicker, more sure. Wherever she'd been the last seven years, that blade of hers had certainly been put to use.

"About time you woke up," she chides, catching his eye. "Day's half gone."

He ignores her, not ready to face the consequences of the night before, and trudges towards a copse of trees at the bottom of the hill to take a piss.

When he returns, she has already set about breaking down the camp and readying the horses.

She says nothing of the night before. In fact, she acts as if nothing out of the ordinary has occurred at all, jabbering away as if she hadn't been keening beneath him mere hours ago.

He begins to wonder if it had all been a very vivid dream. An invention born from his mind after too much drink and a month spent on the road with no company but a sour-faced Stark.

He nearly has himself convinced, until nightfall finds her in his arms once more.

The rest of the journey is passed this way. Each day is spent riding in a fragile sort of companionship. Each night is spent keeping each other's beds.

They are less than a day's ride from Winterfell when he takes her against a tree. It's the first time their coupling isn't under the cover of darkness, but she doesn't seem to mind.

She's wearing a dress (for once) for her reception with her little lord brother. It's a simple grey wool, hardly fit for a lady of her station, but it suits her. The gentle curves he'd only felt in the dark of night are visible in the lines of the gown, and he feels like a green boy, growing hard at the sight.

Her skirts are hiked around her waist, her legs wrapped about him as he pushes her against the tree, claiming her mouth, her neck, her teats. She matches his desperation, as small cool hands find their way inside his tunic, clawing at his back.

It's rough, and clumsy, and over before it's even started. They are both left panting, their breath visible in the cold Northern air, while they unwind from one another. As he watches her set herself to rights, smoothing her skirt and fastening her furs about her neck, a familiar self-loathing settles in his gut.

"This is the last time, girl."

She laughs, high and clear, before pressing a kiss to his burnt cheek. He pulls from her grasp, her kiss smarting like a brand on his scarred flesh.

"For fuck's sake, I'm trying to help you!" he growls. He wants to slap her, to shake her, to scare her. Anything to keep her from reaching for him again. "You keep away from me. I'm a dog, not one of your courteous little lords."

She stills, grey eyes regarding him coolly.

"And I'm not my sister."

Before he can respond, she's on her horse, headed back in the direction of the Kingsroad.

They ride in silence. Each mile closer to Winterfell seems to chip away at the ease that had settled between the two traveling companions over the last month.

_Good. Better she remember the way of things now, before we reach the gate. _

By midafternoon, the walls of the keep have finally come into view. It's not as grand as it had once been, with parts of the outer battlements still destroyed, but the young Lord Stark had certainly wasted no time in rebuilding his home.

Arya reigns in her horse, staring at the walls in the distance. She looks ready to bolt, though whether towards Winterfell or back to King's Landing he cannot tell.

"You're home now, girl," he encourages gruffly.

For the first time all afternoon, she looks at him. There's fear in her eyes, true enough, but something else as well; a frenzied sort of happiness that looks strange on a solemn Stark.

In spite of what had passed that morning, she smiles at him, and bugger it all he still wants her. She was right all those years ago. He is the worst shit in the Seven Kingdoms.

Without warning, she urges her mare into a gallop, kicking up a cloud of dust from the road.

"Are you coming or not?" she calls over her shoulder.

He curses under his breath, spurring his mount follow.

She would be the death of him yet.


	2. A Nameday Gift For No One

No matter what passed between them, she had always been grateful that he never mistook her for anything other than what she was. _She-Wolf. Stark Bitch. Girl. _Now he bows and scrapes with all the rest.

**A Nameday Gift For No One**

She can no longer wear another's face.

The Kindly Man made sure of that when he cast her out of the House of Black and White into the alleyways of Braavos, blind and half-mad.

For the rest of her days her only face would be the one she was born to, that way the Many-Faced-God would make no mistake when he came to stake his claim.

Arya Stark. _Lady_ Arya Stark. It is as strange a face to her as any of the others.

Things were easier in the Red Keep. With sell-swords and foreigners on the Small Council, she was far from the only oddity in the Dragon Queen's court.

But here? Here she is haunted by the girl she once was.

As a child, she always felt so wrongfooted, so unnatural. It was Sansa who was the true lady. Sansa who curtsied, and embroidered, and sang, and never said the wrong thing. Sansa who would marry a lord, and give him babes, and do her duty. All the while, Arya tore her dresses, and skinned her knees, earning lecture after lecture from Septa Mordane and the same glint of disappointment in her mother's eyes.

_Horseface. Underfoot. Weasel. Arry. Nan. Salty. Cat. Beth. Mercy._

All suit her better than her true name.

But she is a Stark of Winterfell. Not even traveling across the Narrow Sea, becoming faceless, could change that. There is no escaping it now. She is a lady.

Even _he_ treats her like a lady now.

No matter what passed between them, she had always been grateful that he never mistook her for anything other than what she was.

_She-Wolf. Stark Bitch. Girl._

Now he bows and scrapes with all the rest.

She wants to scream at him. At all of them. She wants to knock every bastard who bows to her or utters a deferent "my lady' into the dirt until they remember what she is.

_No One._

But she won't. For Bran and Rickon's sake, if for nothing else.

She wonders what Bran must have thought when she arrived at his gates two moons ago, his long lost sister with The Hound at her side. If he had any objections to her escort, he kept them to himself, offering The Hound what hospitality Winterfell had to offer with a steely Stark reserve she had seen so often in her father's face. Gone is the boy who climbed towers and dreamed of knighthood. In his place is only Lord Stark, Warden of the North.

Bran's men are far less welcoming towards the new addition to Winterfell. After all, Sandor Clegane is a Lannister man (even if that Lannister is only Sansa). While none are brave enough to confront the 'Mad Dog of the Saltpans' to his face, plenty of disapproving whispers and jeers are aimed at his back.

A few moons ago, she might have japed with him about the dark looks he receives in the yard and in the hall, but he's avoided her since that awful day by the tree.

_"__This is the last time, girl!"_

He kept true to his word. He's not touched her since that day, and hardly speaks to her unless it is absolutely necessary.

He is a stupid dog. _Sansa's _dog.

Still, she watches him.

His days are spent in the training yard, crossing blades with what men-at-arms are foolhardy enough to challenge him. His nights are spent in his cups, spurning her bed.

He takes to leaving the Keep at night. He waits until after the hall's been cleared from supper, and then he saddles his beast of a horse and rides out the gates.

_Good riddance! Let him crawl back to the Red Keep like the stupid, miserable shit he is!_

Yet every morning when she enters the hall and sees his dark head bowed over a bowl of porridge, still half drunk from the day before, she can't help the wave of relief that washes over her.

He's not rode South. Not yet. _Not today._

Overwrought with curiosity (and fear) she follows him on one of his nightly rides.

He does not go far. Only to the brothel in Winter Town.

She moves silently, tucking herself into a corner of the common area, unnoticed. She may be stuck with her own face, but she still remembers how to melt into the shadows, how to hide in plain sight.

She watches as he drinks cup after cup of wine, red-faced and reeling in his seat.

That first night he leaves the common area in the company of a brunette whore named Mae. He staggers up the steps unsteadily, cursing under his breath, one large hand cupping Mae's arse.

That should be the end of it. What did she care for how he spends his coin? He owes her nothing.

And yet she is drawn to the brothel the next night, and many nights after, watching, unseen, from the shadows.

Some nights he drinks until he passes out, his craggy face planted onto the tabletop, snoring open-mouthed. Other nights he takes a whore to bed.

A petty, childish part of her is pleased when he doesn't seem to show a particular interest in the pretty young red-haired wench over any of the others. She hates herself for it.

By the sixth night she's watched her fill. If he wants to bed whores and drink himself to death while brooding and mooning over Sansa, that is his affair.

He is an idiot. (But so is she).

Her twentieth nameday arrives just as the first spring storm begins to clear. She stopped marking them long ago, and expects this one to pass as silently as all the others.

When Bran surprises her with a feast for the occasion, she bites her tongue. For all her hatred of fuss and courtly pomp, she is moved that her little brother did not forget.

It is a simple feast, but after the privation of the long winter, it seems as grand a banquet as any held in their halls. Bran's had the last few barrels of Dornish red brought up from the cellars, as well as a large quantity of honeyed mead. There are even few minstrels present from White Harbor, a gift from Lord Manderly.

She is surprised by the number of Northern houses in attendance. Spring has not fully taken hold in the North, and travel is not yet easy. Their presence is a testament to the loyalty and respect Bran has gained in his short time as their liege lord.

She is so proud of him, and she thinks, just this once, she does not mind being Lady Arya Stark.

The evening passes pleasantly. She swaps stories with her brother's bannerman and shares bawdy jokes with their men-at-arms. When the minstrels begin to play, she dances with any man willing to stand with her.

She will never admit it to anyone, but she enjoys dancing almost as much as her 'water dancing'.

These aren't the stiff, formal dances of the South, or the intricate dances of the East, but the quick Northern reels of her girlhood.

She remembers cold nights spent indoors, learning to dance. At the time, she had grumbled, unhappy to do anything Sansa deemed as fun. But then Sansa would strike up a tune on her harp, and Arya would forget to sulk. Robb would lift Arya so she stood on his toes as he moved them about the room, all the while playacting he was a puffed-up knight from a song to get her to smile. When his turn came, Jon would fumble through the steps before giving up and tossing her into the air, laughing as he caught her.

She moves from partner to partner, chasing the memory of Sansa's voice and Robb's steady grip and Jon's laugh, until she is spinning off her heels.

_This must be what it is like to fly._

She finally returns to her seat at the high table, flushed and smiling.

She catches one or two bewildered stares from around the hall. Lord Stark's somber sister grinning like a madwoman must be quite a sight.

"Bran never mentioned you were such a fine dancer."

Arya looks to the seat next to her where her goodsister is settled, a cup of sweet honeyed milk in hand.

"If you think that, then you're a poor judge of dancing." Arya winces as soon as the words leave her mouth. She may be a woman grown, but she still has a knack for saying the wrong thing.

Meera does not seem to mind, shrugging off Arya's words.

"Well at least your are not in want for partners!" Meera teases, sipping from her cup. "Any of the rabble worthy of turning into a lord husband?"

Arya rolls her eyes.

While Meera means it in jest, Arya knows it is not far from Bran's intentions. He would never force one of his bannerman on her, but if should she take a liking to one on her own…

Unbidden, her eyes scan the crowd for a familiar hulking figure.

She had spotted him earlier at one of the lower tables, Rickon seated at his side.

For all that he manages to avoid her at every turn, Rickon is a Stark the Hound cannot seem to shake. Since the day they arrived, her youngest brother has taken to following the Hound around the Keep like a lost puppy. And to everyone's surprise, the Hound allows it, gruffly instructing Rickon in the yard or letting the boy chatter happily in his wake.

Arya easily spots Rickon's familiar crown of copper curls, but frowns when she sees the place next to him is empty.

_Surely he has not left! Not this night!_

Mumbling an excuse to Meera, she slips out of the hall and heads for the stables.

She is pleased when she see's his great destrier is still in it's stall, but her relief is short-lived.

"What are you doing in the stables at this hour, my lady?"

She spins on her heel, coming face to face with the horse's owner.

"It's my castle. I may go where I like," she bristles, heat creeping up her neck. "And what of you? Going on a late night ride?"

She hopes to shame him, to make it clear she knows _exactly_ how he spends his nights. But to her annoyance, the great oaf only looks amused, brushing past her into the stall. He reaches for his saddlebag and something twists in her gut.

_He does mean to leave, then._

She tells herself to walk away. Let him ride off to his wine and his whores. What does she care?

A parting barb is set to spill from her lips, when he emerges from the stall, clutching something in his hands.

"Just came to get this," he says gruffly, moving towards her. "Here."

He holds out a long lumpy bundle wrapped in roughspun cloth.

_A nameday gift._

Stunned, she takes the package with unsteady hands, trying to ignore the heavy weight of his stare. She pulls at the twine that binds it and unfolds its cloth wrappings.

It is a sword.

Losing all trepidation, she unsheathes it, examining the blade.

"It's sturdier than your last," he comments, watching as she swings it experimentally. "But it should still serve for your water dancing."

He is right. It is a thin blade, fashioned similarly to Needle. Just right for water dancing.

She lost Needle when the Faceless Men cast her out.

_Bastards probably melted it down into a lump of steel._

Since then she'd made do with borrowed blades, ones she took from strange armories or stole off of dead men, but none of them suited her much. None, till now.

She takes her stance, admiring how easily the sword moves in her hand. It is well made. Castle forged. The blade is longer than Needle, and the balance is weighted to suit someone of her size (not a nine-year-old). It is so perfect in all of its particulars it is almost as if it were made for her.

_It is._

She finally looks up to meet his gaze. His face is as stony and indifferent as it's been since they passed through her brother's gates, but there's something in his eyes, a kind of softness she has seen only a handful of times before.

He did this for _her_.

Before she can think better of it, she drops the sword and throws her arms around his neck, pressing her lips to his. He tenses under her touch, his mouth unresponsive under hers. She has forgotten herself.

Hadn't he made it very clear he wants none of her kisses? That he wants none of her?

Humiliated, she makes to step away, but two great hands grip at her waist, anchoring her against him. His mouth now moves against hers insistently, his tongue brushing against her lower lip, begging for entrance.

She returns his attentions eagerly. Her hands move from around his neck to desperately grasping at his shoulders, brushing her chest against his own.

He maneuvers her against the stall door, a wood beam pressing uncomfortably into her back. She can't bring herself to mind, tugging him closer, until they are firmly melded together.

He stoops to reach her, his hands pressed to the door, bracketing her head. One of his legs is wedged between her own, so that she is straddling his thigh. She ruts against it, breathing a high keening cry into his mouth.

The sound seems to break through the lust-filled fog that surrounds them, and suddenly he is two paces back, panting heavily.

She stays frozen in place against the door, unsure whether he means to reach for her or run.

He does neither. Instead he bends down to pick up the forgotten sword and return it to its scabbard. He holds it out to her, his grey eyes wary but still dark with wanting.

"I take it you like the sword?" The unburnt side of his mouth twists into a smirk.

"Shut up, stupid!" She punches him in the arm, ducking her head to hide the traitorous blush now staining her cheeks. Snatching the blade from him, she studies the well-oiled leather of the scabbard and the three small but gleaming onyx stones studding the pommel. "It's the best gift I received this night," she says quietly, forcing herself to look him in the eye, to make him understand how truly she means it.

He shrugs, scratching his head, uncomfortable with the praise.

"You'll want to name the damned thing, I wager."

"Names are important."

"I suppose they are," he grunts, crossing his arms, the smirk gone from his face. "Will you marry him, then?"

Her eyes fly to him, stunned.

"Who?" she asks. She tries to read his face, but he is suddenly fixated with staring at his boots.

"Whichever highborn cunt in there your lord brother wants to sell you to," he grumbles, nodding his head in the direction hall.

"As if he could," she scoffs. _Bran wouldn't dare._

He finally looks at her. His face remains hard-set, but his shoulders seem to sag some, in what she assumes must be relief.

"True enough. Any man fool enough to wed you is like to find himself gelded on his wedding night."

From another man, she might take such words as an insult, but there is an odd sort of fondness in the Hound's voice as he says them.

"Will you stay?" she asks, the question spilling from her before she can stop it. "In Winterfell, I mean."

She silently curses herself. _He owes you nothing. He's sworn you no vows._

He pauses, sharp grey eyes considering her carefully.

"Aye, I'll stay for a time," he says finally. "Don't have anywhere better to be. Does that suit, my lady?"

She shrugs, biting back the smile pulling at her lips.

"I suppose. There's always a need for fighting men, and you're good for little else. But I have one condition."

He cocks his head to the side, looking more like a dog than ever.

"Aye? And what may that be?"

She fixes him with her best commanding _Lady _Arya Stark stare.

"No more of this 'my lady' nonsense. Agreed?"

He barks out a laugh, and she's glad to hear it.

"So be it, girl."

"I'm no girl," she challenges, chin raised. "I'm twenty today."

A queer look crosses his face that has her toes curling and warmth filling her belly.

"Aye, that you are."

This time when she moves to kiss him, he meets her halfway.

**Author's Note:**

So I'm 100% supposed to be editing/finishing my next chapter of 'Let Us Be Brave' and some of my JonxSansa oneshots. Instead I revisited my long-neglected 'She-Wolf and The Hound' universe and my favorite crackship. I have no self-control. This is my first time writing in Arya's POV. She's one tough broad to get a handle on. Here's hoping it seems at least a little bit in character. Thanks for reading!


End file.
